package main.java.com.rmisorter.sorters;
import java.rmi.RemoteException;

@SuppressWarnings({ "rawtypes", "unchecked"})
public class QuickInsertionSort extends SuperSort {
	private static final long serialVersionUID = 1L;

	public QuickInsertionSort() throws RemoteException {
		super();
	}

	public Comparable[] sort(Comparable[] listToSort) throws RemoteException {
		validateEmptyList(listToSort);
		validateAlreadySortedList(listToSort);
		
	    quickSort(listToSort, 0, (listToSort.length - 1));
	    
	    return listToSort;	
	}
	
    private void quickSort(Comparable[] listToSort, int start, int end) throws RemoteException {
    	InsertionSort insertionSort = new InsertionSort();
    	int left = start, right = end;
    	Comparable pivot;
    	
        if (start < end) {
            if ((end - start) < 9) {
            	insertionSort.insertionSort(listToSort, start, end + 1);
            }
            else {
                pivot = listToSort[start + (end - start) / 2];
                left = start;
                right = end;
                
                while (left <= right)
                {
                    while (listToSort[left].compareTo(pivot) < 0) {
                        left++;
                    }
                    
                    while (listToSort[right].compareTo(pivot) > 0) {
                        right--;
                    }
                    
                    if (left <= right) {
                    	exchangeItems(listToSort, left, right);
                    	left++;
                    	right--;
                    }
                }
                
                if (start < right)
                	quickSort(listToSort, start, right);
            
                if (left < end)
                	quickSort(listToSort, left, end);
            }
        }
    }
    
    private void exchangeItems(Comparable[] listToSort, int left, int right) {
    	Comparable temp = listToSort[left];
    	listToSort[left] = listToSort[right];
    	listToSort[right] = temp;
    }
}
